public class Estado {

	// Responsavel por gerar o id do estado
	private static int gerarID = 0;
	// Armazena o id do estado
	private int id;
	// Armazena o nome do estado
	private final String nome;
	// Armazena se o estado e final
	private boolean eFinal;
	// Essa matriz armazena as transicoes relacionadas a este estado
	// Ele e da forma: transicoes[cardinalidadeAlfabeto+2][cardinalidadeEstados]
	// Precisamos de mais duas colunas devido a possibilidade de transicoes em
	// vazio e outros
	private Estado[][] transicoes;
	// Armazena se o estado e atingivel ou nao
	private boolean atingivel = true;

	// Construtor, inicializa o nome, eFinal, gera um id para o estado e reserva
	// o espaco para a matriz de transicoes
	public Estado(String nome, boolean eFinal, int cardinalidadeAlfabeto,
			int cardinalidadeEstados) {

		this.nome = nome;

		this.eFinal = eFinal;

		this.id = gerarID++;

		this.transicoes = new Estado[cardinalidadeAlfabeto + 2][cardinalidadeEstados];

	}

	// Esse construtor e utilizado quando removemos os nao determinismos da
	// maquina
	public Estado(String nome, boolean eFinal, Estado[][] transicoes) {

		this.nome = nome;

		this.eFinal = eFinal;

		this.id = gerarID++;

		this.transicoes = transicoes;

	}

	// Esse metodo e responsavel por associar as transicoes de estados
	// Para isso, ele busca a primeira ocorrencia de estado nulo no vetor de
	// transicoes associado ao simbolo e e associa o estado destinno
	public void associarTransicao(Estado destino, int posicaoSimbolo) {

		Estado prov = transicoes[posicaoSimbolo][0];

		int pos = 0;

		while (prov != null)
			prov = transicoes[posicaoSimbolo][++pos];

		transicoes[posicaoSimbolo][pos] = destino;

	}

	// Esse metodo devolve o nome do estado
	public String getNome() {

		return nome;

	}

	// Esse metodo devolve se o estado e final ou nao
	public boolean verificarFinal() {

		return eFinal;

	}

	// Esse metodo devolve todas as transicoes do estado
	public Estado[][] getTransicoes() {

		return transicoes;

	}

	// Esse metodo retorna o id do estado
	public int getID() {

		return id;

	}

	// Esse metodo devolve a transicao numero posicao relacionada ao simbolo
	// associado a posicaoSimbolo
	public Estado getTransicao(int posicaoSimbolo, int posicao) {

		return transicoes[posicaoSimbolo][posicao];

	}

	// Esse metodo informa quantas transicoes estao associados ao simbolo
	// representado por posicaoSimbolo
	public int getNumeroTransicoes(int posicaoSimbolo) {

		int cont = 0;

		for (int i = 0; i < transicoes[posicaoSimbolo].length; i++)
			if (transicoes[posicaoSimbolo][i] != null)
				cont++;

		return cont;

	}

	// Esse metodo ordena as transicoes do estado
	public void ordenarTransicoes() {

		for (int i = 0; i < transicoes.length; i++)
			// Primeiramente verificamos se existem multiplas transicoes
			// associadas ao simbolo i em questao
			if (getNumeroTransicoes(i) > 1) {

				Estado[] prov = new Estado[transicoes[i].length];
				int pos = 0;

				// Agora ordenamos ordenar o vetor
				for (int j = 0; j < transicoes[i].length; j++)
					if (transicoes[i][j] != null)
						prov[transicoes[i][j].getID()] = transicoes[i][j];
				for (int j = 0; j < transicoes[i].length; j++)
					if (prov[j] != null)
						transicoes[i][pos++] = prov[j];

			}

	}

	// Esse metodo informa se existem transicoes em vazio partindo deste estado
	// Devolve true em caso afirmativo
	// Vale ressaltar que as transicoes em vazio encontram-se na coluna de
	// indice (transicoes.length - 1)
	public boolean verificarTransicaoVazio() {

		if (transicoes[transicoes.length - 1][0] != null)
			return true;

		return false;

	}

	// Esse metodo transforma o estado em final
	public void setFinal() {

		this.eFinal = true;

	}

	// Devolve todas as transicoes em vazio
	public Estado[] getTransicoesVazio() {

		Estado[] prov = new Estado[transicoes[transicoes.length - 1].length];

		for (int i = 0; i < prov.length; i++)
			prov[i] = transicoes[transicoes.length - 1][i];

		return prov;
	}

	// Esse metodo e responsavel por realizar a juncao dos estados no caso das
	// transicoes em vazio
	// Apos essa juncao, devemos ordenar novamente as transicoes
	public void juntarEstado(Estado estado) {

		Estado[][] transicoesProv = estado.getTransicoes();

		for (int i = 0; i < transicoesProv.length; i++)
			for (int j = 0; j < transicoesProv[i].length; j++)
				if (transicoesProv[i][j] != null)
					insereTransicao(transicoesProv[i][j], i);

		ordenarTransicoes();

	}

	// Esse metodo e responsavel por verificar e inserir uma nova transicao
	private void insereTransicao(Estado estado, int posicao) {

		boolean encontrou = false;

		// Primeiramente checamos se o estado ja se encontra presente na
		// transicao associada ao simbolo de posicao i
		for (int i = 0; i < transicoes[posicao].length; i++)
			if (transicoes[posicao][i] != null)
				if (transicoes[posicao][i].getID() == estado.getID())
					encontrou = true;

		// Se o estado nao estiver presente, o inserimos
		if (!encontrou) {
			int i = 0;

			while (transicoes[posicao][i] != null)
				i++;

			transicoes[posicao][i] = estado;

		}

	}

	// Esse metodo e responsavel por limpar as transicoes em vazio associadas ao
	// estaodo com id indicado, ou seja, transformar estas transicoes em null
	public void removerEstadoTransicaoVazio(int id) {

		for (int i = 0; i < transicoes[transicoes.length - 1].length; i++)
			if (transicoes[transicoes.length - 1][i] != null)
				if (transicoes[transicoes.length - 1][i].getID() == id)
					transicoes[transicoes.length - 1][i] = null;

		ordenarTransicoes();

	}

	// Esse metodo verifica se existem multiplas transicoes no estado
	public boolean verificarMultiplasTransicoes() {

		for (int i = 0; i < transicoes.length; i++) {

			int cont = 0;

			for (int j = 0; j < transicoes[i].length; j++)
				if (transicoes[i][j] != null)
					cont++;

			if (cont > 1)
				return true;

		}

		return false;

	}

	// Esse metodo e responsavel por devolver a primeira ocorrencia de multiplas
	// transicoes
	public Estado[] getMultiplasTransicoes() {

		Estado[] prov;
		int cont = 0;
		int pos = 0;
		boolean encontrou = false;

		for (int i = 0; i < transicoes.length && !encontrou; i++) {

			cont = 0;

			for (int j = 0; j < transicoes[i].length; j++)
				if (transicoes[i][j] != null)
					cont++;

			if (cont > 1) {

				encontrou = true;

				pos = i;

			}

		}

		prov = new Estado[cont];

		for (int i = 0; i < prov.length; i++)
			prov[i] = transicoes[pos][i];

		return prov;

	}

	// Esse metodo e responsavel por remover as multiplas transicoes. Para isso,
	// buscamos todas as transicoes para estados com nome presente no nome do
	// novo estado e removemos
	public void removerMultiplasTransicoes(Estado novo) {

		String[] nomes = novo.getNome().split(",");

		for (int i = 0; i < transicoes.length; i++) {

			boolean transicoesEncontradas = true;

			// Checamos se a quantidade de transicoes associadas ao simbolo na
			// posicao i seja a mesma quantidade de nomes
			if (devolverQuantidadeTransicoes(i) == nomes.length) {
				for (int j = 0; j < nomes.length; j++)
					if (!transicaoPresente(nomes[j], i))
						transicoesEncontradas = false;
			} else
				transicoesEncontradas = false;

			if (transicoesEncontradas) {

				for (int j = 0; j < transicoes[i].length; j++)
					transicoes[i][j] = null;

				transicoes[i][0] = novo;

			}

		}

	}

	// Esse metodo informa se existe uma transicao com o nome informado
	// associado ao simbolo na posicao pos
	private boolean transicaoPresente(String nome, int pos) {

		for (int i = 0; i < transicoes[pos].length; i++)
			if (transicoes[pos][i] != null)
				if (nome.equals(transicoes[pos][i].getNome()))
					return true;

		return false;

	}

	// Esse metodo informa quantas transicoes existem associados ao simbolo na
	// posicao pos
	private int devolverQuantidadeTransicoes(int posicaoSimbolo) {

		int cont = 0;

		for (int i = 0; i < transicoes[posicaoSimbolo].length; i++)
			if (transicoes[posicaoSimbolo][i] != null)
				cont++;

		return cont;

	}

	// Esse metodo verifica se o estado e atingivel ou nao
	public boolean verificarAtingivel() {

		return atingivel;

	}

	// Esse metodo define que o estado e inatingivel
	public void setInatingivel() {

		atingivel = false;

	}

	// Esse metodo verifica se existe uma transicao com o nome indicado
	// Esse metodo e utilizado somente quando o automato e deterministico
	public boolean verificarTransicao(String nome) {

		for (int i = 0; i < transicoes.length; i++)
			if (transicoes[i][0] != null)
				if (nome.equals(transicoes[i][0].getNome()))
					return true;

		return false;

	}

	// Esse metodo reseta o gerador de id
	public static void resetarGeradorID() {

		gerarID = 0;

	}

	// Esse metodo forca um novo id no estado. Isto e necessario quando
	// transformamos um automato finito nao deterministico em deterministico
	private void setID(int novoID) {

		id = novoID;

	}

	// Esse metodo e responsavel por atualizar os ids dos estados
	// Isso e necessario apos removermos os estados inatingiveis
	public void atualizarIDTransicoes(String nome, int novoID) {

		for (int i = 0; i < transicoes.length; i++)
			for (int j = 0; j < transicoes[i].length; j++)
				if (transicoes[i][j] != null)
					if (nome.equals(transicoes[i][j].getNome()))
						transicoes[i][j].setID(novoID);

	}

	// Esse metodo e responsavel por devolver o proximo estado em uma transicao
	public Estado getProximoEstado(int posicaoSimbolo) {

		return transicoes[posicaoSimbolo][0];

	}

}